package 动态规划;

import com.alibaba.fastjson.JSON;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class No343整数拆分 {

    /**
     * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
     *
     * 示例 1:
     * 输入: 2
     * 输出: 1
     * 解释: 2 = 1 + 1, 1 × 1 = 1。
     * 示例 2:
     * 输入: 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
     */

    /**
     * 用动态规划求解,找出最小数的拆分
     * 假设n=10
     * f(0)=0;
     * f(1)=f(0)*1;//最坏的情况就是+1,然后乘积就是乘1了,不变
     * f(2)=max{f(1)*1,f(0)*2};
     * f(3)=max{f(2)*1,f(1)*2,f(0)*3}
     * f(4)=max{f(3)*1,f(2)*2,f(1)*3,f(0)*4}
     * //感觉O(n-1)太慢了,怎么办呢?先试着写一写
     * //写完后:最后表明重复是不可避免的,并且开始时没有考虑(i-j)*j情况出现
     */
    public int integerBreak(int n){

        int[] dp=new int[n+3];//保护我下面写死的情况
        dp[0]=0;
        dp[1]=1;
        dp[2]=1;
        dp[3]=2;//就想写这么多

        for (int i = 4; i <= n; i++) {
            dp[i]=dp[i-1];//先赋予最坏的情况:比前一位多1,就直接乘1了
            for (int j = 1; j < i; j++) {
                /**
                 * 为什么还要(i-j)*j呢?直接拿一个n=4来说明吧
                 * 4应该为[2,2]=4,但是用dp->dp[2]*2,dp[2]为1,导致结果为1*2=2,所以这样做
                 */
                dp[i]=Math.max((i-j)*j,Math.max(dp[i-j]*j,dp[i]));
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        No343整数拆分 n=new No343整数拆分();
        int i = n.integerBreak(10);
        System.out.println(i);
    }

}
